1. Field of the Invention
The present invention relates to computational geometry in general and to determining visibility of points from a predefined point of view in particular.
2. Discussion of the Related Art
Computer graphics employ processing units to determine visibility of points. Visibility determination is the process of determining whether a particular point in space is visible from a specific point of view. Determining the visibility of a surface of an object quickly and efficiently has been a fundamental problem in computer graphics.
Determining visible points is useful for indicating field of view from a specific point, for defining shadow casting for the gaming industry, for the security industry and the like. For example, finding visible points may result in a more clearly visible object enabling to see better the particular features, curves and shapes of the object. In an exemplary case, a computerized image depicting the face of a person can be processed such that the human face contours are visibly shown after the processing. Such processing may be changing the color of some points in case they are not visible, hence distinguishing visible points from non-visible points in the image. After changing the color of the points that are visible from a specific point of view, a person watching the image can then determine if the human face is shown or if the back of the human head is shown.
A point cloud is a set of three-dimensional points describing the outlines or surface features of an object that may be produced by a 3D digitizer. Alternatively, point cloud can also represent some properties in N dimensional space. Evidently, points cannot occlude one another unless they are collinear with the viewpoint. As a result, points in the point cloud are not considered hidden. However, once the surface from which the points are sampled is reconstructed (in 2D or 3D), it is possible to define which of the points are visible to a viewer having a predetermined point of view. A point cloud inherently contains information from which it is possible to extract the visibility of the points to a viewer having a predetermined point of view.
Current solutions achieve points visibility by constructing a surface from the points in the point cloud, and using the surface to determine which of the points is visible. Reconstruction of the surface from the points requires considerable time and computation resources.
In addition, visibility of point clouds has been addressed in the context of rendering images or representations of objects. For example, rendering visibility maps that indicates whether one point can be viewed from another before the data is actually required. This is done by a matrix having values representing the level of visibility from a viewpoint. This way, runtime of O(1) is required to receive an answer concerning visibility and runtime of at least O(n2) is required to prepare the matrix. No solutions having runtime of O(n log n) are suggested in the art. Moreover, camera rotation or change in the field of view requires time-consuming visibility recalculation.
Therefore, it is desirable to provide a method and apparatus for efficiently determining the visible points without constructing a surface of points. Further, such method and apparatus are desired to be implemented using less memory, low complexity (e.g. O(n log n)) and be independent of camera rotation.